#include<iostream>
#include<sstream>
#include<vector>
using namespace std;
struct treenode{
    treenode *left;
    treenode *right;
    int data;
};
treenode * build(const vector<int>& a,int & index){
    if(index>=a.size())return NULL;
    if(a[index]==0){
        index++;
        return NULL;
    }
    treenode * root =new treenode;
    root->data=a[index];
    index++;
    root->left=build(a,index);
    root->right=build(a,index);
    return root;
}
void root_f(treenode *root){
    if(root == NULL) return;
    cout<<root->data<<" ";
    if(root->left)root_f(root->left);
    if(root->right)root_f(root->right);
}
void root_m(treenode *root){
    if(root == NULL) return;
    if(root->left)root_m(root->left);
    cout<<root->data<<" ";
    if(root->right)root_m(root->right);
}
void root_s(treenode *root){
    if(root == NULL) return;
    if(root->left)root_s(root->left);
    if(root->right)root_s(root->right);
    cout<<root->data<<" ";
}
string s;
int main(){
    getline(cin,s);
    stringstream ss(s);
    int n;
    vector<int> a;
    int b;
    while(ss>>b){
        a.push_back(b);
    }
    int c=0;
    treenode * root=build(a,c);
    root_f(root);
    cout<<endl;
    root_m(root);
    cout<<endl;
    root_s(root);
    cout<<endl;
    return 0;
}